{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random,datetime\n",
    "from bisect import bisect_left\n",
    "from math import exp\n",
    "from fractions import Fraction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _generate_parent(length, geneSet, get_fitness):\n",
    "    genes = []\n",
    "    while len(genes) < length:\n",
    "        sampleSize = min(length - len(genes), len(geneSet))\n",
    "        genes.extend(random.sample(geneSet, sampleSize))\n",
    "    fitness = get_fitness(genes)\n",
    "    return Chromosome(genes, fitness)\n",
    "\n",
    "def _mutate_custom(parent, custom_mutate, get_fitness):\n",
    "    childGenes = parent.Genes[:]\n",
    "    custom_mutate(childGenes)\n",
    "    fitness = get_fitness(childGenes)\n",
    "    return Chromosome(childGenes, fitness)\n",
    "\n",
    "\n",
    "def get_best(get_fitness, targetLen, optimalFitness, geneSet, display,\n",
    "             custom_mutate=None, custom_create=None, maxAge=None):\n",
    "    if custom_mutate is None:\n",
    "        def fnMutate(parent):\n",
    "            return _mutate(parent, geneSet, get_fitness)\n",
    "    else:\n",
    "        def fnMutate(parent):\n",
    "            return _mutate_custom(parent, custom_mutate, get_fitness)\n",
    "\n",
    "    if custom_create is None:\n",
    "        def fnGenerateParent():\n",
    "            return _generate_parent(targetLen, geneSet, get_fitness)\n",
    "    else:\n",
    "        def fnGenerateParent():\n",
    "            genes = custom_create()\n",
    "            return Chromosome(genes, get_fitness(genes))\n",
    "\n",
    "    for improvement in _get_improvement(fnMutate, fnGenerateParent, maxAge):\n",
    "        display(improvement)\n",
    "        if not optimalFitness > improvement.Fitness:\n",
    "            return improvement\n",
    "\n",
    "\n",
    "def _get_improvement(new_child, generate_parent, maxAge):\n",
    "    parent = bestParent = generate_parent()\n",
    "    yield bestParent\n",
    "    historicalFitnesses = [bestParent.Fitness]\n",
    "    while True:\n",
    "        child = new_child(parent)\n",
    "        if parent.Fitness > child.Fitness:\n",
    "            if maxAge is None:\n",
    "                continue\n",
    "            parent.Age += 1\n",
    "            if maxAge > parent.Age:\n",
    "                continue\n",
    "            index = bisect_left(historicalFitnesses, child.Fitness, 0,\n",
    "                                len(historicalFitnesses))\n",
    "            proportionSimilar = index / len(historicalFitnesses)\n",
    "            if random.random() < exp(-proportionSimilar):\n",
    "                parent = child\n",
    "                continue\n",
    "            bestParent.Age = 0\n",
    "            parent = bestParent\n",
    "            continue\n",
    "        if not child.Fitness > parent.Fitness:\n",
    "            # same fitness\n",
    "            child.Age = parent.Age + 1\n",
    "            parent = child\n",
    "            continue\n",
    "        child.Age = 0\n",
    "        parent = child\n",
    "        if child.Fitness > bestParent.Fitness:\n",
    "            bestParent = child\n",
    "            yield bestParent\n",
    "            historicalFitnesses.append(bestParent.Fitness)\n",
    "\n",
    "\n",
    "class Chromosome:\n",
    "    def __init__(self, genes, fitness):\n",
    "        self.Genes = genes\n",
    "        self.Fitness = fitness\n",
    "        self.Age = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_fitness(genes, equations):\n",
    "    fitness = Fitness(sum(abs(e(genes)) for e in equations))\n",
    "    return fitness\n",
    "\n",
    "def display(candidate, startTime, fnGenesToInputs):\n",
    "    timeDiff = datetime.datetime.now() - startTime\n",
    "    symbols = \"xyza\"\n",
    "    result = ', '.join(\"{} = {}\".format(s, v)\n",
    "                       for s, v in\n",
    "                       zip(symbols, fnGenesToInputs(candidate.Genes)))\n",
    "    print(\"{}\\t{}\\t{}\".format(\n",
    "        result,\n",
    "        candidate.Fitness,\n",
    "        timeDiff))\n",
    "\n",
    "\n",
    "def mutate(genes, sortedGeneset, window, geneIndexes):\n",
    "    indexes = random.sample(geneIndexes, random.randint(1, len(genes))) \\\n",
    "        if random.randint(0, 10) == 0 else [random.choice(geneIndexes)]\n",
    "    window.slide()\n",
    "    while len(indexes) > 0:\n",
    "        index = indexes.pop()\n",
    "        genesetIndex = sortedGeneset.index(genes[index])\n",
    "        start = max(0, genesetIndex - window.Size)\n",
    "        stop = min(len(sortedGeneset) - 1, genesetIndex + window.Size)\n",
    "        genesetIndex = random.randint(start, stop)\n",
    "        genes[index] = sortedGeneset[genesetIndex]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Fitness:\n",
    "    def __init__(self, totalDifference):\n",
    "        self.TotalDifference = totalDifference\n",
    "\n",
    "    def __gt__(self, other):\n",
    "        return self.TotalDifference < other.TotalDifference\n",
    "\n",
    "    def __str__(self):\n",
    "        return \"diff: {:0.2f}\".format(float(self.TotalDifference))\n",
    "\n",
    "\n",
    "class Window:\n",
    "    def __init__(self, minimum, maximum, size):\n",
    "        self.Min = minimum\n",
    "        self.Max = maximum\n",
    "        self.Size = size\n",
    "\n",
    "    def slide(self):\n",
    "        self.Size = self.Size - 1 if self.Size > self.Min else self.Max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_unknowns(numUnknowns, geneset, equations,fnGenesToInputs):\n",
    "        startTime = datetime.datetime.now()\n",
    "        maxAge = 50\n",
    "        window = Window(max(1, int(len(geneset) / (2 * maxAge))),\n",
    "                        max(1, int(len(geneset) / 3)),\n",
    "                        int(len(geneset) / 2))\n",
    "        geneIndexes = [i for i in range(numUnknowns)]\n",
    "        sortedGeneset = sorted(geneset)\n",
    "\n",
    "        def fnDisplay(candidate):\n",
    "            display(candidate, startTime, fnGenesToInputs)\n",
    "\n",
    "        def fnGetFitness(genes):\n",
    "            return get_fitness(genes, equations)\n",
    "\n",
    "        def fnMutate(genes):\n",
    "            mutate(genes, sortedGeneset, window, geneIndexes)\n",
    "\n",
    "        optimalFitness = Fitness(0)\n",
    "        best = get_best(fnGetFitness, numUnknowns, optimalFitness,\n",
    "                                geneset, fnDisplay, fnMutate, maxAge=maxAge)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_2_unknowns():\n",
    "    geneset = [i for i in range(-5,5) if i != 0]\n",
    "\n",
    "    def fnGenesToInputs(genes):\n",
    "        return genes[0], genes[1]\n",
    "\n",
    "    def e1(genes):\n",
    "        x, y = fnGenesToInputs(genes)\n",
    "        return x + 2 * y - 4\n",
    "\n",
    "    def e2(genes):\n",
    "        x, y = fnGenesToInputs(genes)\n",
    "        return 4 * x + 4 * y - 12\n",
    "    equations = [e1, e2]\n",
    "    solve_unknowns(2, geneset, equations, fnGenesToInputs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = 1, y = -5\tdiff: 41.00\t0:00:00\n",
      "x = 3, y = -3\tdiff: 19.00\t0:00:00\n",
      "x = 4, y = -3\tdiff: 14.00\t0:00:00\n",
      "x = 4, y = -1\tdiff: 2.00\t0:00:00.000999\n",
      "x = 1, y = 2\tdiff: 1.00\t0:00:00.002992\n",
      "x = 2, y = 1\tdiff: 0.00\t0:00:00.018948\n"
     ]
    }
   ],
   "source": [
    "test_2_unknowns()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "30x + 15y = 600\n",
    "15x + 20y = 200"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = 22, y = -26\tdiff: 720.00\t0:00:00\n",
      "x = 27, y = -26\tdiff: 495.00\t0:00:00.001004\n",
      "x = 45, y = -26\tdiff: 405.00\t0:00:00.001004\n",
      "x = 42, y = -26\tdiff: 360.00\t0:00:00.001004\n",
      "x = 41, y = -26\tdiff: 345.00\t0:00:00.001004\n",
      "x = 32, y = -26\tdiff: 270.00\t0:00:00.001004\n",
      "x = 14, y = 5\tdiff: 215.00\t0:00:00.001004\n",
      "x = 14, y = -1\tdiff: 205.00\t0:00:00.001993\n",
      "x = 20, y = -1\tdiff: 95.00\t0:00:00.001993\n",
      "x = 20, y = -2\tdiff: 90.00\t0:00:00.001993\n",
      "x = 20, y = -3\tdiff: 85.00\t0:00:00.002998\n",
      "x = 21, y = -3\tdiff: 70.00\t0:00:00.002998\n",
      "x = 21, y = -5\tdiff: 60.00\t0:00:00.002998\n",
      "x = 22, y = -5\tdiff: 45.00\t0:00:00.002998\n",
      "x = 23, y = -6\tdiff: 25.00\t0:00:00.009972\n",
      "x = 23, y = -7\tdiff: 20.00\t0:00:00.018961\n",
      "x = 24, y = -8\tdiff: 0.00\t0:00:00.135640\n"
     ]
    }
   ],
   "source": [
    "def test_2_unknowns2():\n",
    "    geneset = [i for i in range(-100,100) if i != 0]\n",
    "\n",
    "    def fnGenesToInputs(genes):\n",
    "        return genes[0], genes[1]\n",
    "\n",
    "    def e1(genes):\n",
    "        x, y = fnGenesToInputs(genes)\n",
    "        return 30 *x + 15 * y - 600\n",
    "\n",
    "    def e2(genes):\n",
    "        x, y = fnGenesToInputs(genes)\n",
    "        return 15 * x + 20 * y - 200\n",
    "    equations = [e1, e2]\n",
    "    solve_unknowns(2, geneset, equations, fnGenesToInputs)\n",
    "test_2_unknowns2()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6x - 2y + 8z = 20\n",
    "### y + 8x * z = -1\n",
    "### 2z * 6/x + 3y/2 = 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_3_unknowns():\n",
    "        geneRange = [i for i in range(-5, 5) if i != 0]\n",
    "        geneset = [i for i in set(\n",
    "            Fraction(d, e)\n",
    "            for d in geneRange\n",
    "            for e in geneRange if e != 0)]\n",
    "        def fnGenesToInputs(genes):\n",
    "            return genes\n",
    "\n",
    "        def e1(genes):\n",
    "            x, y, z = genes\n",
    "            return 6 * x - 2 * y + 8 * z - 20\n",
    "\n",
    "        def e2(genes):\n",
    "            x, y, z = genes\n",
    "            return y + 8 * x * z + 1\n",
    "\n",
    "        def e3(genes):\n",
    "            x, y, z = genes\n",
    "            return 2 * z * Fraction(6, x) \\\n",
    "                   + 3 * Fraction(y, 2) - 6\n",
    "\n",
    "        equations = [e1, e2, e3]\n",
    "        solve_unknowns(3, geneset, equations, fnGenesToInputs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = 2/5, y = -4, z = -3/4\tdiff: 55.50\t0:00:00\n",
      "x = 2/5, y = -3, z = -3/4\tdiff: 55.00\t0:00:00.000995\n",
      "x = -3/5, y = -3, z = -3/4\tdiff: 29.70\t0:00:00.000995\n",
      "x = -3/5, y = -5, z = -3/4\tdiff: 21.50\t0:00:00.001963\n",
      "x = -2/3, y = -5, z = -3/4\tdiff: 20.00\t0:00:00.005951\n",
      "x = -3/5, y = -5, z = -2/3\tdiff: 19.90\t0:00:00.019914\n",
      "x = -1/4, y = -4, z = -1/4\tdiff: 18.00\t0:00:00.036870\n",
      "x = -1/5, y = -4, z = -1/5\tdiff: 17.48\t0:00:00.045844\n",
      "x = 1/2, y = -4/5, z = 1/5\tdiff: 17.20\t0:00:00.059808\n",
      "x = 1/3, y = -4/5, z = 1/5\tdiff: 15.53\t0:00:00.059808\n",
      "x = 1/3, y = -5/4, z = 1/5\tdiff: 14.86\t0:00:00.061280\n",
      "x = 1/3, y = -3/2, z = 1/5\tdiff: 14.48\t0:00:00.063252\n",
      "x = 5/3, y = -3/2, z = 1/5\tdiff: 14.38\t0:00:00.067241\n",
      "x = 3/4, y = -5, z = 3/4\tdiff: 2.50\t0:00:00.068236\n",
      "x = 3/5, y = -5, z = 3/4\tdiff: 2.30\t0:00:00.071230\n",
      "x = 3/5, y = -5, z = 2/3\tdiff: 2.03\t0:00:00.076215\n",
      "x = 2/3, y = -5, z = 3/4\tdiff: 0.00\t0:00:00.092175\n"
     ]
    }
   ],
   "source": [
    "test_3_unknowns()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
